% -*- LaTeX -*-
\documentstyle[german,umlaut,a4wide,twocolumn]{article}
\sloppy

\def\pfe{{\bf pfe}}

\pagestyle{myheadings}
\markright{pfe---das Portable Forth Environment}

\begin{document}

\title{Das Portable Forth Environment \\
\large Eine einfache Realisierung von Forth in C}
\author{Dirk Zoller}
\date{Mannheim, 14.\ April 1994}
\maketitle

\abstract{Es wird eine Implementation des draft proposed American
  National Standard (dpANS) für die Sprache Forth beschrieben. Das
  beschriebene System hat den Arbeitsnamen \pfe, setzt den dpANS
  vollständig um und ist selbst in ANSI-C geschrieben, so daá es
  leicht portabel ist auf verschiedene Rechnerumgebungen. Obwohl das
  System den aktuellen Standard realisiert, ist der Ansatz in vieler
  Hinsicht traditionell und so einfach wie m÷glich. Dieses Papier
  erläutert einige der De"-sign"-ent"-schei"-dun"-gen, die dabei zu
  treffen waren, und gibt Hinweise zum Einsatz und zur Portierung von
  \pfe.\footnote{\pfe\ kann per anonymous ftp bezogen werden:
      roxi.rz.fht-mannheim.de:/pub/languages/forth/pfe-x.x.x.tar.gz}}


\section{Ziele}
\label{sec:ziele}

Der kommende ANSI-Standard \cite{dpans} für die Sprache Forth ist
wesentlich umfangreicher als alle bisherigen Standards für diese
Sprache.  Gleichzeitig vermeidet er die Regelung von
Implementationsdetails, eine Eigenschaft früherer Standards, die
zunehmend deren Akzeptanz beeinträchtigte.

Implementatoren, die bisher aus dem engen Korsett des fig-Modells oder
dem 16-Bit-Diktat des FORTH-83-Standards ausbrachen, sahen sich auf
sich selbst gestellt und waren gezwungen, nicht nur in
Implementationsdetails abzuweichen, sondern wesentliche
Spracheigenschaften frei zu gestalten. Die Folge war eine Phase des
Wildwuchses, wo kein Forth wie das andere war. Sie geht nun
hoffentlich zu Ende.

\paragraph{Verfügbarkeit und Portabilität} Jetzt ist es wichtig,
daá treue und vollständige Implementationen des Standards
bereitstehen, die es erm÷glichen, Quelltexte an den Standard
anzupassen, und die auf die noch z÷gernden Anbieter den notwendigen
Anpassungsdruck ausüben.

Der Umfang des Standards macht seine voll"-stän"-di"-ge Umsetzung mit
den bisherigen Methoden -- in Assembler oder mittels eines
Meta"-com"-pi"-lers -- zu einer nicht"-tri"-via"-len Aufgabe, für die
die Anbieter offensichtlich noch Zeit brauchen.

\pfe\ wurde dagegen aus zwei Gründen in ANSI-C geschrieben: Es sollte
in vollem Umfang rasch zur Verfügung stehen und es sollte auf sovielen
Plattformen wie m÷glich -- und das heiát zuallererst auf UNIX -- zur
Verfügung stehen.

\pfe\ läuft z.Z.\ auf verschiedenen UNIX-Derivaten\footnote{bisher
  sind erprobt: Linux, AIX 3.2x, HP-UX 8.x, Domain-OS, Sun-OS, Ultrix
  4.3 RISC, Irix.} sowie auf DOS (ab 386) und OS/2 ab 2.0. Anpassungen
an weitere 32-Bit-Systeme, deren C-Compiler gewisse UNIX-ähliche
Funktionen in der Library haben,\footnote{In erster Näherung kann man
  vermuten, daá \pfe\ mit geringem Aufwand portabel ist auf ein
  System, wenn dort auch GNU-C läuft.} dürften einfach sein. Seit
fig-Forth ist kein freies Forth-System mehr so gleichartig auf so
vielen verschiedenen Rechnern gelaufen.

\paragraph{Vertrautheit} Damit ein zur Verfügung stehendes System
aber auch benutzt wird, müssen sich potentielle Benutzer darin
wohlfühlen. In \pfe\ wurde deshalb einiger Aufwand getrieben, den
interaktiven ``Look and feel'' von Forth-Systemen auf typischen
Einplatzsystemen (PC, Atari,\dots) trotz der Portabilität zu erhalten.
So wird eine Tastatureingabe nicht einfach mit der C-Funktion {\sl
  gets()\/} abgeholt, sondern das Verhalten von {\tt EXPECT}
nachgebildet. Die Kommandozeile erlaubt das Zurückholen und das
Edieren alter Eingaben.  Cursor-Positionierung und Text-Attribute sind
m÷glich, Funktionstasten k÷nnen mit Forth-Worten belegt werden und ein
vollständiger Block-Editor ist integriert.

Zum Wohlfühlen in einem System geh÷rt auch, daá es vertraut ist.
Deshalb wurden bekannte Worte, die nicht den Weg in den Standard
gefunden haben, trotzdem aufgenommen. Soweit es nicht im Widerspruch
zum dpANS steht, gibt es alles aus fig-Forth und FORTH-83 sowie
einiges aus Laxen\&Perry's F83. Die Fädelungstechnik ähnelt dem
traditionellen ``indirect threading'' und die Datenstrukturen im
Dictionary sind ähnlich den schon vor 15 Jahren von fig-Forth
benutzten.

\paragraph{Stabilität} ist eine Eigenschaft, ohne die kein System das
Vertrauen der Benutzer erwirbt, das sie veranlaát darauf aufbauend
Stunden und Tage in ihre Entwicklungen zu investieren. Stabil ist aber
nur ein einfaches System. Ein weiterer Grund, bei den
Designentscheidungen auf bewährte und verstandene Konzepte zu bauen.

\subsection{Was fehlt}

Im Interesse der Einfachheit und Stabilität wurde auf verschiedene
Dinge bewuát verzichtet, weil sie eine Gr÷áenordnung mehr Komplexität
in das System hineingetragen hätten oder im Widerspruch zum Ziel der
Portabilität stehen:
\begin{itemize}
\item die Fähigkeit sich selbst zu übersetzen
\item ein Assembler
\item die Fähigkeit, Maschinencode zu erzeugen
\item die Fähigkeit, Libraries aufzurufen.\footnote{Speziell für Linux
    existiert eine L÷sung von Kevin Haddock.}
\item Multitasking
\end{itemize}


\section{Design}
\label{sec:design}

Schreibt man ein Forth-System in C, werden viele Dinge, die bei einer
As"-sem"-bler-Im"-ple"-men"-ta"-tion Kopfzerbrechen bereiten k÷nnen,
sehr einfach.  So ist ein in C programmierbares System von vornherein
zur Flieákommaarithmetik, Freispeicherverwaltung usw.\ fähig. Sehr
viele Forth-Worte brauchen also nur den entsprechenden Funktionsaufruf
zu tun. Es gibt aber auch Bereiche, in denen C gegen den Strich zu
bürsten ist, damit Forth herauskommt.

Ich m÷chte mich hier auf die zu bewältigenden Schwierigkeiten
konzentrieren. Damit hoffe ich das Verständnis der entsprechenden
Passagen im Quelltext zu erleichtern. Es wird sich allerdings zeigen,
daá bei Beachtung einiger einfacher Regeln Änderungen und
Erweiterungen am C-Quelltext leicht m÷glich sind, auch ohne sich in
die Tiefen der Exception-Behandlung einzulesen.

\subsection{Datentypen}
\label{sec:datentypen}

Im Gegensatz zu Forth ist modernes C eine streng typisierte
Sprache\footnote{Wer's nicht glaubt, versuche einmal ein gr÷áeres
  Programm {\em ohne Warnungen\/} durch mehrere verschiedene
  ANSI-C-Compiler zu bringen.}. Forth macht zwar keinen Unterschied
zwischen Adresse und ganzer Zahl, muá aber diese Laxheit ausgleichen
durch präzisere Forderungen an das Verhältnis der wenigen elementaren
Typen zueinander.

Implementiert man dpANS-Forth in ANSI-C, muá man es beiden recht
machen. Im C-Quelltext folgen daraus viele explizite Typumwandlungen
(``type casts''). Diese ansonsten bedenkliche Praxis führt hier nicht
zu Problemen, weil die konsistenten Anforderungen von Forth an die
beteiligten Datentypen eingehalten werden.

Insbesondere fordert der dpANS, daá eine Adresse und eine einfach
genaue ganze Zahl dieselbe Gr÷áe im Speicher haben, und nennt solch
eine Einheit {\sl ``cell''\/}. C erlaubt uns darauf einzugehen, indem
wir unter mehreren ganzzahligen Datentypen denjenigen auswählen, der
dieselbe Gr÷áe wie ein Zeiger hat. Dieser Datentyp wird zum
ganzzahligen Grundtyp unter dem Namen {\tt Cell}.

Der Standard fordert neben dem ganzzahligen Grundtyp noch einen
doppelt so groáen ganzzahligen Datentyp.\footnote{Tatsächlich hat der
  Standard ein Herz und hat diese Forderung in einen optionalen
  ``double number extension word set'' ausgelagert.} Nachdem wir aber
für Forth' ganzzahligen Grundtyp schon {\em irgendeinen\/}
ganzzahligen C-Typ nehmen muáten, k÷nnen wir nicht davon ausgehen, daá
der C-Compiler unter dem Namen {\tt long} noch etwas gr÷áeres für uns
hat.  Die Arithmetik mit Forth' doppelt genauen Zahlen muá also unter
Verwendung von {\tt Cell} allein nachgebildet werden. Bei der
Gelegenheit fällt es dann auch nicht weiter schwer, die in Forth
übliche Reihenfolge der beiden Zellen einer doppelt genauen Zahl auf
dem Stack einzuhalten.

Bei den laufenden Systemen sind durchweg die einfach genauen Zahlen 32
Bit groá und die doppelt genauen Zahlen 64 Bit. Es spricht aber nichts
dagegen, auf einem entsprechenden System 64 Bit groáe einfach genaue
und 128 Bit groáe doppelt genaue Zahlen zu haben. Eine Reduktion des
Systems auf 16/32 Bit wäre -- aus anderen Gründen als der Arithmetik
-- schwieriger.


\subsection{Die Forth-Maschine in C}

Es sollen m÷gliche Implementationsvarianten abgewogen werden, die
gewählte erklärt und begründet werden. Dazu wird das Modell einer
virtuellen Maschine herangezogen, das vom Forth-79 Standard
definiert\footnote{vgl.\ \cite{dpans} S.\ 193} aber auch schon in
fig-Forth verwendet wurde.\footnote{eine detaillierte Diskussion
  dieser virtuellen Maschine und ihrer Grund"-opera"-tio"-nen
  realisiert auf verschiedenen CPUs findet sich in \cite{zech} S.\ 27}

Der dpANS erwähnt die virtuelle Maschine nicht mehr. Er stellt sich
auf einen abstrakteren Standpunkt und redet über die verschiedenen
"`Semantiken"' von Worten zur Übersetzungs- und Laufzeit. Das ist gut
so, denn längst ist es gängige Implementationspraxis, die genaue
Arbeitsweise der virtuellen Maschine zugunsten von
prozessorspezifischen Optimierungen und pers÷nlichen Vorlieben zu
ignorieren, dabei nur mehr oder weniger genau darauf achtend, daá die
oberste Ebene -- eben die Semantik -- noch genauso aussieht, wie man
es von einem Forth erwartet.

Andererseits steht die virtuelle Maschine nicht im Widerspruch zum
Standard und ist nach wie vor geeignet, ein Standard-System zu
treiben.

\paragraph{Low-Level/High-Level}
Ein Forth-System muá elementare Grundoperationen bereitstellen.
Normalerweise sind dies in Assembler geschriebene Worte, auch genannt
Low-Level- oder Code-Worte oder Primitives. Geeignete Primitives
\begin{itemize}
\item manipulieren Daten- und Returnstack
\item machen die Arithmetik
\item führen bedingte und unbedingte Sprünge aus
\item verarbeiten zur Laufzeit literale Konstanten der verschiedenen
  Typen
\item greifen auf lokale Variablen zu
\end{itemize}

High-Level-Worte sind dagegen die compilierten Worte, die in
irgendeiner Form aus Adress- oder Token-Listen bestehen, die vom {\sl
inneren Interpreter\/}, der Operation {\sl next\/} der virtuellen
Maschine, abgearbeitet werden.

Daneben gibt es noch die sogenannten ``runtimes''. In
Assembler-Implementationen sind das Code-Stücke, die in {\sl next\/}
enden, aber nicht als Primitives auftreten. Vielmehr bestimmen sie das
Laufzeitverhalten von Variablen, Konstanten und vor allem von
High-Level-Worten.

Nachdem der innere Interpreter ({\sl next\/}) jedes Wort bedingungslos
anspringt, muá für jedes Wort ausführbarer Code existieren. Die
runtimes stellen diesen ausführbaren Code z.B.\ für Variablen bereit.
Das runtime {\sl nest\/} ist das ausführbare Stückchen Code für eine
High-Level-Definition.

\subsubsection{Die virtuelle Maschine}
Ein klassisches ``indirect threaded'' Forth birgt in sich -- ohne daá
der Benutzer darauf direkten Zugriff hätte -- eine virtuelle Maschine
mit vier Registern, davon zwei Stackpointer in die beiden Stacks, und
einigen Grundoperationen.

Die Register der virtuellen Maschine sind: Daten-Stack-Pointer {\sl
SP\/} und Return-Stack-Pointer {\sl RP\/}, der Instruction-Pointer
{\sl IP\/} und ein weniger einleuchtendes aber wichtiges Register
namens {\sl W\/}, das stets in das Datenfeld\footnote{früher auch PFA
genannt} der aktuell ausgeführten Code-Definition zeigt.

Um all das zu erreichen, was der dpANS vorschreibt, genügt es nach wie
vor, wenn ein Forth-System -- neben einer geeignet ausgewählten Menge
von Primitives -- die elementaren Grundoperationen der virtuellen
Maschine realisiert:
\begin{description}
\item[next] eine gewisse Menge (je weniger, desto besser) von
  Maschinenbefehlen, die zum nächsten auszuführenden Primitive
  springen. Wohlgemerkt ist das im klassischen Forth {\em kein\/}
  Unterprogrammsprung, sondern ein Weiterspringen, von dem es keine
  Rückkehr gibt. Die Kontrolle über den Programmfluá wird durch die
  anderen Grundoperationen ausgeübt. Mit den Registern der virtuellen
  Maschine und einem Hilfsregister $X$ läát sich die Aktion {\sl
    next\/} so beschreiben:
\[
\begin{array}{rcl}
  W & \leftarrow & (IP) \\
  IP & \leftarrow & IP + \mbox{1 Cells} \\
  X & \leftarrow & (W) \\
  W & \leftarrow & W + \mbox{1 Cells} \\
  \multicolumn{3}{l}{\mbox{Sprung nach }X}
\end{array}
\]
\item[nest] ist der zunächst von einer :-Definition ausgeführte Code.
  Legt den Instruction-Pointer {\sl IP} auf dem Return-Stack ab und
  setzt den {\sl IP} auf den Beginn des Datenfeldes der aktuell
  ausgeführten Definition:
\[
\begin{array}{rcl}
  RP & \leftarrow & RP - \mbox{1 Cells} \\
  (RP) & \leftarrow & IP \\
  IP & \leftarrow & W \\
  \multicolumn{3}{l}{\mbox{Aktion von }next}
\end{array}
\]
{\sl Next} führt nun das erste Wort aus der Liste von Worten aus, die
das compilierte High-Level-Wort ausmachen.
\item[unnest] Umkehrfunktion von {\sl nest}, kehrt zum rufenden Wort
  zurück indem der von {\sl nest} gesicherte Wert vom Return-Stack
  zurückgeholt wird:
\[
\begin{array}{rcl}
  IP & \leftarrow & (RP) \\
  RP & \leftarrow & RP + \mbox{1 Cells} \\
  \multicolumn{3}{l}{\mbox{Aktion von }next}
\end{array}
\]
\item[does] Mit {\sl nest} verwandt ist eine Funktion der virtuellen
  Maschine zur Unterstützung von {\tt CREATE...DOES>}-Definitionen.
  Ein mit einem Definitionswort {\sf DEF} definiertes Wort {\sf W} muá
  im Sinne einer high-level De"-fi"-ni"-tion compilierten Code
  ausführen, der aber nicht im Datenfeld des Wortes {\sf W} steht,
  sondern irgendwo anders, vorzugsweise innerhalb des Wortes {\sf
    DEF}.
\end{description}

Nur auf die Operation {\sl unnest\/} hat der Programmierer direkten
Zugriff, sie wird durch das Wort {\tt EXIT} repräsentiert. Die übrigen
Grundoperationen der virtuellen Maschine sind dem Forth-Programmierer
nicht zugänglich. {\sl nest\/} wird vom Compiler bei Bedarf eingeplant
und {\sl next\/} bildet das Ende jeder Code-Definition, tritt für den
Programmierer nur dann in Erscheinung, wenn er selbst
Code-Definitionen hinzufügt, also den in viele Systeme integrierten
Assembler benutzt.

\subsubsection{Erste Ideen zur Umsetzung in C}

Wir werden einen C-Compiler nicht dazu bewegen k÷nnen, unsere in C
geschriebenen Primitives mit Befehlen entsprechend der {\sl
  next\/}-Operation abzuschlieáen, wie man das in einer
Assembler-Implementation macht. Auáerdem k÷nnen wir ihn nicht dazu
überreden, irgendwo einfach hinzuspringen, ohne sich um die Rückkehr
zu kümmern.

Ruft er ein als C-Funktion definiertes Primitive auf, wird er
sicherlich auf einem Unterprogramm-Sprung bestehen. Dem Primitive wird
er entsprechend einen Unterprogramm-Rücksprung anfügen. Der innere
Interpreter wird in erster Näherung\footnote{Die {\sl
    W\/}-Systemvariable wird hier ebenso ignoriert wie m÷gliche
  L÷sungen für die Operationen {\sl nest/unnest\/}} zu einer Schleife:

\begin{verbatim}
for (;;) (*ip++) ();
\end{verbatim}

{\sl IP} ist hier ein Zeiger auf Zeiger auf Funktionen, die Primitives
realisieren. Compilierte High-Level-Definitionen sind also Listen von
Zeigern auf die Funktionen, die die hineincompilierten Primitives
realisieren.

Die Operation {\tt (*ip++)()} kann man sich als {\sl next} vorstellen,
die {\tt for}-Schleife drumherum hebt den Effekt des
Unterprogramm-Sprungs wieder auf.

\paragraph{Alternativen} Will man die Schleife vermeiden, darf man das
einzelne Primitive nicht zu einer C-Funktion machen. Daraus folgt, daá
alle Primitives Teil einer einzigen C-Funktion sein müssen. Dies führt
zur ``giant switch''-L÷sung: Hierbei werden der innere Interpreter und
die Realisierung aller Worte in eine einzige C-Funktion geschrieben.
Diese C-Funktion besteht im wesentlichen aus einem {\sl
  switch\/}-Statement.  Compilierte Forth-Worte sind Listen von Codes,
deren jeder einen Zweig in dem {\sl switch\/}-statement auswählt. Der
innere Interpreter sieht unvollständig ungefähr so aus:
\begin{verbatim}
for (;;)
  switch (*ip++)
    {
      case DROP: sp++; break;
      case DUP:  --sp; sp [0] = sp [1];
                 break;
      ...
\end{verbatim}
Mit etwas Glück ist diese Methode sehr schnell, nämlich wenn der
Compiler die wesentlichsten Systemvariablen {\tt sp}, {\tt rp} und
{\tt ip}, die lokal zu der groáen Funktion deklariert sind, in
Prozessorregister legt.

Nachdem dpANS-Forth aber sehr umfangreich ist, wird diese Funktion
entsprechend {\em sehr\/} groá. Es ist unwahrscheinlich, daá eine so
groáe Funktion noch gut optimiert -- oder überhaupt von allen
Compilern akzeptiert -- wird. Ausgliederung von aufwendigeren Worten
in eigene Funktionen ist erschwert durch den Umstand, daá wichtige
Systemvariablen lokal zur Haupt-Funktion sind. Jegliche Änderung
erfordert das neue Übersetzen praktisch des gesamten Systems. Gründe
genug, diese Variante nicht weiter in Betracht zu ziehen.

\subsubsection{Probleme}

Die erste Idee \verb$for(;;) (*ip++)()$ eignet sich bei näherer
Betrachtung nur zur Ausführung von Worten, die ausschlieálich aus
Primitives zusammencompiliert sind. Denn es wird angenommen, daá
compilierter Forth-Code aus Listen von Zeigern auf ausführbare
Funktionen besteht. Ein High-Level-Wort ist aber keine ausführbare
C-Funktion.

Die L÷"-sung besteht natürlich in der Ein"-füh"-rung einer wei"-teren
In"-direk"-tion: Ein compiliertes Forth-Wort ist ein Zeiger auf einen
Platz, in dem ein Zeiger steht, der über die Bedeutung des Wortes
entscheidet. Der innere Interpreter wird zu:
\begin{verbatim}
for (;;) (**ip++) ();
\end{verbatim}
Daraus und aus der angestrebten Traditionalität ergibt sich eine
vorläufige Struktur für den Kopf einer Funktion im Dictionary:
\begin{center}
\begin{tabular}{|c|}       \hline
Countbyte               \\ \hline
Name                    \\ \hline
Link                    \\ \hline
CFA                     \\ \hline
Body                    \\
$\cdots$                \\ \hline
\end{tabular}
\end{center}
Wie üblich werden also Name und Realisierung eines Wortes beieinander
ins Dictionary geschrieben. CFA kann man jetzt als C-Funktions-Adresse
lesen. Ihr Sinn ist derselbe wie in traditionellem indirect threaded
Forth derjenige der Code Field Address: Dorthin wird verzweigt zur
Ausführung des Wortes. Primitives haben hier die Adresse einer
C-Funktion stehen, die die Semantik des Wortes bereitstellt und keinen
Body. High-level-Definitionen haben hier einen Zeiger auf eine
Runtime-Funktion (in C) stehen, die die im Body beginnende Liste von
compilierten Adressen zu interpretieren beginnt: {\sl nest}.

Wie kommt die Runtime-Funktion {\sl nest} zu dem Body der Funktion,
von der aus sie aufgerufen wurde? Sie kann ihn etwas trickreich aus
{\sl IP} schlieáen: \verb$ip = &ip [-1][1]$ (mit einigen Type-Casts).
Besser man erleichtert ihr diese Aufgabe indem man im inneren
Interpreter die Variable {\sl W} der virtuellen Maschine einführt:
\begin{quote}
\begin{verbatim}
for (;;)
  {
    w = *ip++;
    (*w) ();
  }
\end{verbatim}
\end{quote}
Mit dieser endgültigen Form des inneren Interpreters lauten {\sl nest}
und {\sl unnest}:
\begin{quote}
\begin{verbatim}
nest () {
  *--rp = ip;
  ip = ++w;
}
unnest () {
  ip = *rp++;
}
\end{verbatim}
\end{quote}

Ein weiteres Problem ergibt sich mit Definitionsworten. Wie gesagt ist
für alle Definitionsworte der Code in der CFA eines von ihnen
definierten Wortes derselbe. Das Datenfeld beginnt zwingend
unmittelbar hinter der CFA. Wo also kann vermerkt werden, {\it von
  welchem} Definitionswort ein Wort definiert
wurde?\footnote{Assembler-Implementationen generieren hier zur
  Laufzeit ein paar Maschinenbefehle, die in die CFA als ausführbarer
  Code eingetragen werden, und die in den high-level Code überleiten,
  der die Laufzeit-Semantik des Definitionswortes bereitstellt. Eine
  C-Implementation kann das nicht.} Die wenig befriedigende L÷sung
besteht in der Einführung eines weiteren Zeigers {\tt aux} in den Kopf
jeder Definition, der im Fall einer von einem Definitionswort
definierten Definition diese Information enthalten kann:
\begin{center}
\begin{tabular}{|c|}       \hline
Countbyte               \\ \hline
Name                    \\ \hline
Link                    \\ \hline
Aux                     \\ \hline
CFA                     \\ \hline
Body                    \\
$\cdots$                \\ \hline
\end{tabular}
\end{center}
Dieser Zeiger hilft glücklicherweise auch bei anderen Gelegenheiten:
Er stellt z.B.\ den Zusammenhang her zwischen der compilierten
Laufzeitsemantik von Kontrollstrukturen und der Definition, die diese
Laufzeitsemantik compiliert hat. Dadurch kann der Decompiler {\tt SEE}
zu einem compilierten {\tt ?BRANCH} entscheiden, ob er von einem {\tt
  IF} oder einem {\tt WHILE} her stammt und eine entsprechend
strukturierte Ausgabe erzeugen.

\subsection{Das Dictionary}

Das Dictionary ist in klassischen Forth-Implementationen der eine
lineare Speicherbereich, in dem sich alle Forth-Worte -- Namen und
Realisierung -- sowie statisch allozierte Daten in bunter Mischung
beieinander befinden. Moderne Implementationen zeigen eine starke
Tendenz, diesen Bereich aufzuteilen in Symboltabelle, einen Bereich
für Maschinencode und einen für High-level-Definitionen und statisch
allozierten Speicher.\footnote{Die Motive dafür sind teilweise
  unseri÷s: Wenn es nämlich vor allem darum geht, einer ebenso
  misratenen wie verbreiteten Speicherarchitektur ein biáchen mehr
  Raum abzuringen.}

\pfe\ -- traditionell wie es ist -- bleibt bei der einen groáen
Struktur für Namen und Daten. Lediglich der vom C-Compiler erzeugte
Maschinencode liegt auáerhalb.

\subsubsection{Struktur}

Die Namen werden sind wie üblich in einer linearen Liste organisiert.
Zuviel der Semantik von Forth hängt von diesem Ansatz ab, als daá man
ihn ohne gr÷áeres Kopfzerbrechen über Bord werfen k÷nnte. Die Liste
ist allerdings -- weitgehend transparent -- aufgeteilt wird in mehrere
``Threads'', wovon einer durch eine Hash-Funktion auf dem Namen des
Wortes ausgewählt wird.\footnote{Diese L÷sung habe ich in einem
  CSI-Forth gesehen.} Man k÷nnte andersherum sagen: Das Dictionary ist
eine kleine Hash-Tabelle mit groáem linear verkettetem
Überlaufbereich. Es bedarf keiner komplizierteren Ansätze: Die so
erreichte Geschwindigkeit der Dictionary-Suche ist voll befriedigend.

\subsubsection{Wortlisten}

Die Dictionary-Struktur kann vom Compiler nicht ohne groáen manuellen
Aufand etwa als initialisiertes Feld von {\tt char} angelegt werden.
Deshalb werden die Forth-Worte im C-Quelltext in einfacheren Tabellen
organisiert, die die Zuordnung von Namen und auszuführendem Code sowie
Eigenschaften wie {\tt IMMEDIATE} enthalten. Beim Systemstart wird aus
diesen Tabellen das Dictionary gebaut.

Diese Tabellen, eine zunächst technisch motivierte Vorstufe des
Dictionary, k÷nnen auch als ``Word Sets'' aufgefaát werden, wie sie
der Standard kennt. Sie erlauben, den Quelltext des Systems modular
aufzubauen entlang der Vorgabe des Standards, jeden Word Set in einer
eigenen Eingabedatei, die abgeschlossen wird von einer Tabelle, die
die in dieser Eingabedatei definierten Worte geschlossen bereitstellt
und die Implementationsdetails kapselt.


\section{Erweiterung}

Einen Assembler bietet \pfe\ nicht. Man kann es aber leicht durch
C-Funktionen erweitern, was allerdings eine neue Übersetzung des
Systems mit dem C-Compiler erfordert und insofern in der täglichen
Arbeit ein schwacher Trost ist.

Dem C-Programmierer bietet der Rest des Systems folgendes
Programmiermodell:
\begin{description}
\item[Datentypen:] Mit den Objekten aus Sicht von Forth kompatible
  Objekte in C sind als die folgenden {\tt typedefs} bekannt:
\begin{description}
\item[\tt Cell] eine Einheit auf dem Stack, Integer-Typ mit
  Vorzeichen, zuweisungskompatibel mit Zeigertypen.
\item[\tt uCell] eine Einheit auf dem Stack, Integer-Typ ohne
  Vorzeichen.
\item[\tt dCell] eine doppelt genaue Zahl mit Vorzeichen, {\tt struct}
  bestehend aus {\tt Cell hi} und {\tt uCell lo}.
\item[\tt udCell] wie {\tt dCell}, vorzeichenlos.
\item[\tt void (*pcode) (void)] ist ein Zeiger auf eine ein Primitive
  realisierende C-Funktion, die also der Gestalt {\tt void primitive
    (void)} ist. Zur Vermeidung von Namenskollisionen enden die Namen
  all dieser C-Funktionen in einem Tiefstrich. Zur Erleichterung der
  Definition gibt es das Makro {\tt code(NAME)}, das den Funktionskopf
  \verb$void NAME_(void)$ erzeugt. Im Kopf jedes Wortes steht ein
  solcher Zeiger auf die auszuführende Funktion.
\item[\tt pcode *CFA] ist der Typ des Execution Tokens, ein Zeiger auf
  die Position im Kopf eines Wortes, wo der Zeiger auf dieas Wort
  realisierende C-Funktion steht.
\end{description}

\item[Register der virtuellen Maschine] sind global deklarierte
  C-Variablen:
\begin{description}
\item[\tt Cell *sp] Daten-Stackpointer
\item[\tt CFA *ip] Instruktionszeiger. Zeigt in die Liste compilierter
  Worte, deren jedes jeweils genau das Execution Token, also ein
  Zeiger des Typs {\tt CFA} ist.
\item[\tt CFA **rp] Der Return-Stack dient zur Sicherung des {\tt ip},
  der Stapelzeiger ist also ein Zeiger auf den Typ des {\tt ip}.
\item[\tt CFA w] Das W-Register der virtuellen Maschine, hier kann ein
  Primitive seine eigene CFA ablesen. Zugriff auf den Body des Wortes
  über {\tt ({\it typ} *)\&w[1]}.
\end{description}

\item[Systemvariablen] Weil die Art der Speicherung der
  Systemvariablen sich ändern k÷nnte, gibt es zum Zugriff auf die in
  Forth definierten Systemvariablen Makros mit nahenliegenden Namen.
  So kann in C-Funktionen z.B.\ auf den DP unter dem Namen \verb$DP$
  zugegriffen werden usw.

\item[Funktionen] Das System enthält hunderte von C-Funktionen, wovon
  natürlich nicht jede in ihrer jetzigen Form garantiert -- oder gar
  dokumentiert -- werden kann. Beispiele:
\begin{description}
\item[\tt void abortq (char *fmt, ...);] gibt -- mit den Fähigkeiten
  von printf() ausgestattet -- eine Fehlermeldung aus und führt
  \verb$-2 THROW$ aus.
\item[\tt void type (char *s, Cell n)] gibt eine Zeichenkette wie
  \verb$TYPE$ aus.
\item[\tt char *word (char del)] wie das Forth-Wort \verb$WORD$, liest
  ein Wort aus dem Eingabestrom in den Speicher ab {\tt HERE} und
  übergibt diese Stelle als Funktionsergebnis.
\item[\tt void run\_forth (CFA xt);] führt ein beliebiges (auch
  High-level) Forth Wort aus. Enthält den inneren Interpreter.
\end{description}

\item[Makros] erleichtern die Anpassung von C an Forth sehr, weil sich
  darin viele der notwendigen Type-Casts verbergen lassen. Einige
  Beispiele:
\begin{description}
\item[\tt POP(T,P,X)] liest ein Objekt des Typs {\tt T} über den
  Zeiger {\tt P} in die Variable {\tt X}, unabhängig von den
  tatsächlichen Typen der Operanden. Erh÷ht {\tt P} entsprechend.
\item[\tt PUSH(T,X,P)] Umkehrung zu {\tt POP}, schreibt ein Objekt
  {\tt X} des Typs {\tt T} in einen zu kleineren Adressen hin
  wachsenden Stapel mit Stapelzeiger {\tt P}.
\item[\tt RPUSH(X)] legt ein Objekt der Gr÷áe einer Cell auf den
  Return-Stack.
\item[\tt RPOP(X)] holt eine Cell vom Return-Stack.
\item[\tt FLAG(X)] macht aus {\tt X} ein Forth-Flag, also 0 bzw.\ -1.
\item[\tt COMMA(X)] schreibt das Objekt {\tt X} der Gr÷áe 1 Cell ins
  Dictionary.
\end{description}

\end{description}

Will man das System zum Beispiel um einen für ein bestimmtes
Betriebssystem wichtigen Satz von Worten erweitern, bietet sich die
Anlage einer entsprechenden Quelltextdatei an. Sie enthält alle
system- oder aufgabenspezifischen C-Funktionen, die in eine Reihe von
C-Funktionen münden, die die Gestalt von Forth-Primitives haben, also
mit dem Makro {\tt Code ({\it name})} deklariert sind. Diese
Primitives werden in eine Wortliste zusammengefaát, die beim System
registriert wird\footnote{Zur Zeit durch Eintrag in die Tabellen
  innerhalb der Funktion {\tt preload\_dictionary()} in der Datei {\tt
    dictnry.c}} und so beim Start von \pfe\ mit ins Dictionary geladen
wird.

Vollständiges Beispiel:
\begin{small}
\begin{verbatim}
#include "forth.h"
#include "support.h"

Code (user_added_primitive)
{
  outs ("\nThis is a sample primitive."
        " See src/yours.c "
        "for it's definition.\n");
}

LISTWORDS (your) =
{
  CO ("USER-ADDED-PRIMITIVE",
       user_added_primitive),
};
COUNTWORDS (your, "Your kernel extensions");
\end{verbatim}
\end{small}

Das Makro {\tt LISTWORDS} deklariert eine Wort"-lis"-ten-Struk"-tur,
die zu Initialisieren ist mithilfe der Makros:
\begin{center}
\begin{tabular}{lp{4cm}}
\tt CO(NM,PCODE)        & gew÷hnliches Wort \\
\tt CI(NM,PCODE)        & immediate Wort \\
\tt CS(NM,SEM)          & Compiler Erweiterung \\
\tt SV(NM,VAR)          & Systemvariable \\
\tt SC(NM,VAR)          & Forth-Konstante, deren Wert aus
                          einer Variablen stammt \\
\tt OC(NM,VAL)          & normale Konstante \\
\tt VO(NM,RUNTM)        & {\tt WORDLIST} \\
\end{tabular}
\end{center}
Das Makro {\tt COUNTWORDS} zählt schlicht die Anzahl Worte in der
Liste und stellt sie zur Einbindung bereit.


\section{Ausblick}

\pfe\ wird sich entsprechend seiner Bedeutung weiterentwickeln. Zur
Zeit scheint Bedarf an einem solchen System zu bestehen. Allerdings
setzen die eingangs begründeten Design-Prinzipien der Entwicklung
Grenzen. Was sich nicht mit überschaubarem Aufwand und portabel machen
läát, wird nicht mit Priorität behandelt. Es bleiben als {\em
  denkbare} Entwicklungsrichtungen:
\begin{itemize}
\item Bereitstellung eines Metacompilers auf \pfe. Nicht mit dem Ziel
  \pfe\ selbst damit zu übersetzen, sondern um es als
  Entwicklungsplattform für Mikro"-con"-trol"-ler-Pro"-gram"-mie"-rung
  einsetzen zu k÷nnen.
\item Einbindung in eine grafische Benutzeroberfläche, evtl.\ das
  X-Window-System.
\item Bereitstellung einfacher Grafikbefehle
\item Nuetzliche Eigenschaften, wie z.B.\ die Speicherung compilierter
  Module.
\item Multitasking.
\item Bessere Unterstützung von noch mehr Rechnern.
\end{itemize}


\begin{thebibliography}{99}

\bibitem{dpans} American National Standards Institute: {\sl draft
    proposed\/} American National Standard for Information Systems --
  Programming Languages -- Forth (X3J14 dpANS-6 -- June 30, 1993)

\bibitem{fig} Forth Interest Group: {\sl fig-FORTH Installation
    Manual, Glossary, Model, Editor\/}, Version 1.3, San Carlos, CA,
  1980

\bibitem{forth83} FORTH Standards Team: {\sl FORTH-83 Standard\/},
  Mountain View, CA, 1983

\bibitem{zech} Zech, Ronald: {\sl Die Programmiersprache Forth\/},
  München: Franzis, 1983

\end{thebibliography}


\end{document}
